/*
 * @lc app=leetcode.cn id=76 lang=java
 *
 * [76] 最小覆盖子串
 */

// @lc code=start
class Solution {
    public String minWindow(String s, String t) {
        if(s==null || t==null || s.length()==0 || t.length()==0 || s.length()<t.length()) return "";
        int[] need = new int[128];

        int left = 0,right = 0;
        int count = t.length();
        int start = 0;
        int size = Integer.MAX_VALUE;

        for(int i=0; i<t.length(); i++){
            need[t.charAt(i)]++;        // 记录t中字符出现的次数,别的位置都是0
        }

        while(right < s.length()) {
            char c = s.charAt(right);
            if(need[c] > 0) count--;    // 如果是t中的字符--命中,则count--

            need[c]--;                  // 不管是不是t中的字符,都要--

            if(count == 0) {   // 如果count==0,说明t中的字符都命中了
                // 移动left指针,缩小窗口
                while(need[s.charAt(left)] < 0) {   // 如果s中的字符出现次数大于t中的字符出现次数,则--
                    need[s.charAt(left)]++;
                    left++;
                }

                if(right - left + 1 < size) {   // 更新窗口大小
                    start = left;
                    size = right - left + 1;
                }

                need[s.charAt(left)]++;
                left++;
                count++;
            }

            right++;
        }

    return size == Integer.MAX_VALUE ? "" : s.substring(start, start+size);
    }
}
// @lc code=end

